量子計算

量子力学の原理を利用した計算手法。
古くにはフォン・ノイマンにより1982年に提案されている。
有名な利用法はピーター・ショアよって1995年に提案されたショアのアルゴリズム（素因数分解が多項式時間で計算可能）であり、これにより量子計算に注目が集まった。
とはいえ、このようなアルゴリズムを動かすには非常に多くの量子ビット（量子計算の単位）とある程度の時間が必要であり、原理的にノイズに対して極めて弱い量子計算機は現実的ではなかった。しかし、これまた1995年にショアによって提案された量子誤り訂正符号によって実現性を帯びた。
2020年現在では量子誤り訂正符号を組み込んだ大規模な量子計算機はまだ実現されていない。2019年にGoogleが「量子超越性を達成」と発表した53量子ビットの量子コンピュータなど、数十量子ビットが現状の限界である。Shorのアルゴリズムで2048ビットのRSA暗号を解読するには6000といった数の誤り訂正された量子ビットが必要であり（出典）、その1つの誤り訂正された量子ビット一つを実現する為にまたたくさんの物理量子ビットが必要になる。よってこういったものの実現には、（鋭意開発されているけれども）まだ50年とか100年とかの時間が必要と言われている。
一方、今実現しつつあるような、誤り訂正がない50～100量子ビット程度の量子計算機はNISQ(Noisy Intermadiate-Scale Quantum)計算機と言われ、こういったものの有効な利用法についても研究が行われている。

• Quantum Native Dojo
  • 量子計算ベンチャーのQunaSys社方面の人々によって書かれた量子計算入門ドキュメント。おすすめ。
  • 行列計算さえ分かれば物理の知識はなくても読める
• 量子コンピュータの基礎から応用まで/quantum summit 2019
  • 同QunaSys社のスライドだが、非常によくまとまっていると思う。
• 量子計算で出来ること・出来ないこと
  • 日本物理学会誌2019年2月号に掲載された森前さんの文。計算量理論の面から見た量子計算機の性質および現状についてまとめられている。
• とても強い計算量クラスのコンピュータとその実現方法 - Qiita
  • 諸々の計算量クラスについて直感的に書かれているおもしろ記事。
• Quantum Computing in the NISQ era and beyond
  • “NISQ”を定義したPreskillの文書。NISQとはどういうものであるか、どういう応用が考えられているかについて俯瞰している。

文献

• What are some good books for learning quantum computation? - Quora: 文献案内

包括的なもの

• Wilde, Mark M. Quantum information theory. Cambridge University Press, 2013.
  • 量子情報理論の詳細な教科書。
  • [1106.1445] From Classical to Quantum Shannon Theoryで第2版の原稿が公開されている。
• Physics 219 Course Information
  • Preskillのカリフォルニア工科大学での量子計算の講義の講義ノート。
• Lidar, Daniel A., and Todd A. Brun, eds. Quantum error correction. Cambridge university press, 2013.
  • 量子誤り訂正理論についての教科書。いろいろな人が寄稿している。

個別的なもの

• [1802.08227] Quantum linear systems algorithms: a primer
  • 連立一次方程式を効率よく解く量子アルゴリズムであるHarrow-Hassidim-Lloyd (HHL)アルゴリズムに関して。